C/C++ Users Group Library 1996 July/C-C++ Users Group Library July 1996.iso/listings/v_10_01/1001075a

Text File | 1991-11-20 | 6.0 KB | 219 lines

/*
 *      Traversal of multiple binary trees
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define BIGINT  (~(1 << ((8*sizeof(int))-1)))   /* maximum integer */
#define NNODES  25      /* the number of nodes per tree */
#define NTREES  10      /* the number of binary trees to traverse */

/* binary tree node definition */
typedef struct  node    {
        struct  node    *left;          /* left sub-tree */
        struct  node    *right;         /* right sub-tree */
        int             key;            /* current node value */
}       NODE;

/***********************************************************************
 * the following section is the single threaded example
 ***********************************************************************/
#ifdef  SINGLE_THREAD

/* stack frame definition */
typedef struct frame    {
        struct node     *data;          /* the node being stacked */
        struct frame    *next;          /* the next stack entry */
}       FRAME;

/* push a tree node onto the stack */
void Push(FRAME **stackp, NODE *treep) {
FRAME *temp;

        assert(treep != NULL);
        temp = malloc(sizeof(FRAME));
        assert(temp != NULL);
        temp->data = treep;
        temp->next = *stackp;
        (*stackp) = temp;
}

/* get the top data item from the stack (without popping) */
int Top(FRAME *stackp) {
NODE    *temp;

        assert(stackp != NULL);
        temp = stackp->data;
        return(temp->key);
}

/* print the lowest value of all N trees */
void DisplayLowest(FRAME *stackp[], int *lowest) {
int current;
int topvalue;
int temp=BIGINT;
int i;

        /* for each tree in the list... */
        for (i=0; i < NTREES; i++) {
                /* if the tree has not been completely traversed, */
                if (stackp[i] != NULL) {
                        /* get the current key of this tree */
                        topvalue = Top(stackp[i]);
                        /* compare the current key with the other trees */
                        if (topvalue < temp) {
                                /* save the current tree number and its key */
                                current = i;
                                temp = topvalue;
                        }
                }
        }
        printf("key = %d\n", temp);
        *lowest = current;
}

/* removes and returns the top entry from the stack */
NODE *Pop(FRAME **stackp) {
FRAME *temp;
NODE *data;

        temp = *stackp;
        *stackp = (*stackp)->next;
        data = temp->data;
        free(temp);
        return(data);
}

/* traverse the right sub-tree */
void TraverseRightSub(FRAME **stackp) {
NODE *temp;
FRAME *sframe;

        /* find the right sub-tree of the current node */
        temp = Pop(stackp);
        temp = temp->right;

        /* traverse the sub tree as far left as possible */
        while (temp != NULL) {
                Push(stackp, temp);
                temp = temp->left;
        }
}

/* determine if there are unvisited nodes */
int StacksExist(FRAME *stackp[]) {
int i;

        for (i = 0; i < NTREES; i++){
                if (stackp[i] != NULL)
                        return(1);
        }
        return(0);
}

void MergeTrees(NODE *treep[]) {
FRAME *stackp[NTREES];
int i;

        /* preload all stacks */
        for (i = 0; i < NTREES; i++) {
                stackp[i] = NULL;
                while (treep[i] != NULL) {
                        Push(&stackp[i], treep[i]);
                        treep[i] = treep[i]->left;
                }
        }
        do {
                DisplayLowest(stackp, &i);
                TraverseRightSub(&stackp[i]);
        } while(StacksExist(stackp));
}

/***********************************************************************
 * the following section is the multi threaded example
 ***********************************************************************/
#else

#include <multi_c.h>

/* print the contents of a node (wait until it is the lowest key) */
void    PrintNode(NODE *tree) {
static  int     CurrentKey = BIGINT;

        /* wait until this node contains the lowest key value */
        do {
                if (CurrentKey > tree->key)
                        CurrentKey = tree->key;
                MtCYield();
        } while (CurrentKey != tree->key);
        /* reinitialize the current key */
        CurrentKey = BIGINT;
        printf("key = %d\n", tree->key);
}

/* recursively visit the nodes in a tree */
void    PrintTree(NODE *tree) {

        if (tree != NULL) {
                PrintTree(tree->left);
                PrintNode(tree);
                PrintTree(tree->right);
        }
}

/* traverse multiple binary trees */
void    MergeTrees(NODE **trees) {
int     i;

        /* create a thread for each tree... */
        for (i = 0; i < NTREES; i++) {
                MtCCoroutine(PrintTree(&trees[i]));
        }
}

#endif

/* recursively add a node to the tree */
void    AddKey(NODE **treep, int key) {

        if ((*treep) == NULL) {
                (*treep) = malloc(sizeof(NODE));
                assert(*treep != NULL);
                (*treep)->left = NULL;
                (*treep)->right = NULL;
                (*treep)->key = key;
        } else {
                if (key < (*treep)->key) {
                        AddKey(&((*treep)->left), key);
                } else {
                        AddKey(&((*treep)->right), key);
                }
        }
}

/* build a tree of NNODES random keys */
void    BuildTree(NODE **treep) {
int     i;

        for (i = 0; i < NNODES; i++) {
                AddKey(treep, rand());
        }
}


void    main() {
NODE    *trees[NTREES];
int     i;

        /* randomly build the trees */
        for (i = 0; i < NTREES; i++) {
                trees[i] = NULL;
                BuildTree(&trees[i]);
        }
        /* traverse the trees as a single tree */
        MergeTrees(trees);
}